package 我的Java学习_算法基础.day_02;

public class _021_性能对比 {
    public static void main(String[] args) {
        int[] a = new int[10000*1000];
        for(int i = 0;i<a.length;i++){
            a[i]=i+1;
        }
        long now = System.currentTimeMillis();
        int target = 10000*1000;
        int index =search(a,target);
        long times = System.currentTimeMillis()-now;
        System.out.println("找到元素，下标为："+index+" 用时（ms）:"+times);
        now = System.currentTimeMillis();
        index = BinarySearch(a,0,a.length-1,target);
        times = System.currentTimeMillis()-now;
        System.out.println("找到元素，下标为："+index+" 用时（ms）:"+times);
    }
    private static int search(int[] array,int key){
        for(int i = 0;i<array.length;i++){
            if(array[i]==key){
                return i;
            }
        }
        return -1;
    }
    private static int BinarySearch(int[] array,int low,int high,int key){
        if(low>high){
            return -1;
        }
        int mid = low+((high-low)>>1);
        int midVal=array[mid];
        if(key>midVal){
            return BinarySearch(array,mid+1,high,key);
        }else if(key<midVal){
            return BinarySearch(array,low,mid-1,key);
        }else{
            return mid;
        }
    }
}
